import java.util.*;

public class Test {
    //
}
class Solution
{
    int m, n;
    public int cutOffTree(List<List<Integer>> f)
    {
        m = f.size(); n = f.get(0).size();
        List<int[]> trees = new ArrayList<>();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(f.get(i).get(j) > 1)
                    trees.add(new int[]{i, j});

        Collections.sort(trees, (a, b) ->
        {
            return f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
        });
        int bx = 0, by = 0;
        int ret = 0;
        for(int[] next : trees)
        {
            int a = next[0], b = next[1];
            int step = bfs(f, bx, by, a, b);
            if(step == -1) return -1;
            ret += step;
            bx = a; by = b;
        }
        return ret;
    }
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0 ,0};
    public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey)
    {
        if(bx == ex && by == ey) return 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        q.add(new int[]{bx, by});
        vis[bx][by] = true;
        int step = 0;
        while(!q.isEmpty())
        {
            int sz = q.size();
            step++;
            while(sz-- != 0)
            {
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for(int i = 0; i < 4; i++)
                {
                    int x = a + dx[i], y = b + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && f.get(x).get(y)
                            != 0 && !vis[x][y])
                    {
                        if(x == ex && y == ey) return step;
                         q.add(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }

        }
        return -1;
    }
}

